//给你一个字符串 word 和一个整数 numFriends。 
//
// Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中： 
//
// 
// word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。 
// 所有分割出的字符串都会被放入一个盒子中。 
// 
//
// 在所有回合结束后，找出盒子中 字典序最大的 字符串。 
//
// 
//
// 示例 1： 
//
// 
// 输入: word = "dbca", numFriends = 2 
// 
//
// 输出: "dbc" 
//
// 解释: 
//
// 所有可能的分割方式为： 
//
// 
// "d" 和 "bca"。 
// "db" 和 "ca"。 
// "dbc" 和 "a"。 
// 
//
// 示例 2： 
//
// 
// 输入: word = "gggg", numFriends = 4 
// 
//
// 输出: "g" 
//
// 解释: 
//
// 唯一可能的分割方式为："g", "g", "g", 和 "g"。 
//
// 
//
// 提示: 
//
// 
// 1 <= word.length <= 5 * 10³ 
// word 仅由小写英文字母组成。 
// 1 <= numFriends <= word.length 
// 
//
// Related Topics 双指针 字符串 枚举 👍 20 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-06-04 14:18:32
 * @description 3403.从盒子中找出字典序最大的字符串 I
 
 */
 
public class FindTheLexicographicallyLargestStringFromTheBoxI {
    public static void main(String[] args) {
    //测试代码
    FindTheLexicographicallyLargestStringFromTheBoxI fun = new FindTheLexicographicallyLargestStringFromTheBoxI();
    Solution solution= fun.new Solution();
    solution.answerString("aann",2);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //枚举所有的切割方案，然后计算字典序，超时
    Set<String> ans=new HashSet<>();
    public String answerString1(String word, int numFriends) {
        dfs(word, numFriends,new ArrayList<>(), 0);
        return helper(ans);
    }

    private String helper(Set<String> ans) {
        String max = "";
        for (String s : ans) {
            if (s.compareTo(max) > 0) {
                max = s;
            }
        }
        return max;
    }

    private void dfs(String word, int numFriends, List<String> path, int idx) {
        if(numFriends==0||idx==word.length()){
            if(numFriends==0&&idx==word.length()){
                ans.addAll(new ArrayList<>(path));
            }
            return;
        }

        for (int i = idx; i < word.length(); i++) {
            path.add(word.substring(idx,i+1));
            dfs(word,numFriends-1,path,i+1);
            path.remove(path.size()-1);
        }
    }


    // 直接枚举
    /*
    * numFriends = 1 时，直接返回 word
    * 当 numFriends > 1 时，枚举所有可能的切割方式，取字典序最大的字符串。
    * 其中最大长度为min(n-numFriends+1,n-i)，
    * 至少要分割程numFriends个字符串，所以每次切割的长度不能超过n-numFriends+1。
    * */
    public String answerString2(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        int n = word.length();
        String res = "";
        for (int i = 0; i < n; i++) {

            String s = word.substring(i, Math.min(i + n - numFriends + 1, n));
            if (res.compareTo(s) <= 0) {
                res = s;
            }
        }
        return res;
    }
    // 双指针
    /*
    * 对枚举方法，确定左端点是i后，则取左端点i和右端点为min(n-numFrieds+1,n-i)的最大字典序子串。
    * 可以证明，不存在一个比i字典序更大的子串
    *
    * */
    //找到字典序最大的子串
    //维护两个指针i和j，i指向当前最大字典序子串的起始位置，j指向下一个可能的起始位置。
    //比较从i和j开始的子串，找到第一个不同的子串，如果j开始的子串字典序更大，则更新i为j的位置，并将j更新为j+1或i+k+1（k为相同字符的长度）。
    //否则，跳过已经比较过的部分
    public String lastSubstring(String s) {
        int i = 0, j = 1, n = s.length();
        while (j < n) {
            int k = 0;
            // 找到第一个不同的字符，因为如果相同，则从i开始的一定更大，如果全部一样，最终也是返回原串
            while (j + k < n && s.charAt(i + k) == s.charAt(j + k)) {
                k++;
            }
            // 如果j开始的子串字典序更大，则更新i为j的位置，并将j更新为j+1或i+k+1（k为相同字符的长度）。
            if (j + k < n && s.charAt(i + k) < s.charAt(j + k)) {
                int t = i;
                i = j;
                //为了防止回退，直接跳到+k的位置
                j = Math.max(j + 1, t + k + 1);
            } else {
                // 如果j开始的字典序较小，则不更新i，直接把j更新为+k的位置
                j = j + k + 1;
            }
        }
        return s.substring(i);
    }
    //根据numFriends的值，返回字典序最大的子串
    //如果numFriends为1，直接返回word。
    //如果numFriends大于1，找到字典序最大的子串last，然后返回last的前n-numFriends+1个字符。
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        String last = lastSubstring(word);
        int n = word.length(), m = last.length();
        return last.substring(0, Math.min(m, n - numFriends + 1));
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
